1. Field of Invention
Embodiments of the invention relate generally to image transformations. More specifically, at least one embodiment relates to methods for determining a transformation that aligns two images.
2. Discussion of Related Art
Image alignment or registration is employed in a wide variety of fields including cartography, medical imaging systems and machine vision systems to name a few. In general, proper alignment is achieved by identifying a transformation of an image relative to the image with which it is being aligned. Image alignment or registration may be used in various applications. For example, two images of the same subject may be “overlaid” on one another once they are aligned. In addition, adjacent images of a common subject may be aligned to generate a large image from a plurality of adjacent images. Further, image alignment may be employed to determine a change in position of the subject of the image or the camera that is generating the images.
Image registration may be used to evaluate a first image when compared with a second image of the same subject or to generate a “fused” image that combines features from a plurality of images. In cartography multiple images may be combined to create a fused image that combines features of images that are properly aligned, for example, a satellite image may be overlaid with an image of a topographic map. In medicine, information from a first imaging system (an MRI system) may be combined with information from a second imaging system (a computer tomography system) to assist in better monitoring a patient's condition.
In a further medical imaging example, processes may also employ image registration to align two images which are acquired as follows: a first image acquired before injection of a colored liquid; and a second acquired after injection of the liquid. A subtraction operation is then performed on the images to highlight colored features (e.g., veins). Image registration is employed prior to the subtraction operation to account for movement of the subject.
Image registration may also be used with an “image stitching” or “image mosaicing” operation in which multiple images of a scene are taken from various positions and/or angles. The images are registered and then combined to form a single larger and/or higher resolution image. For example, these processes may be employed to: in cartography, combine aerial photographs of land; to create a panoramic image; in astronomy, to create a large image of the sky; or to combine multiple smaller images adjacent one another to construct a large image.
Further uses of image registration processes include: camera calibration, in which camera distortion parameters (e.g., barrel or pin-cushion distortions) are estimated so that they may be compensated for; in “super-resolution,” where a high resolution image of a scene is generated using multiple lower resolution images of the same subject which are precisely aligned; and to determine a position of a camera with respect to an object having a known position. The preceding are just some of the uses for an image registration process that aligns two or more images. The utility of image registration continues to expand with the continued increase in the capabilities of both image capture systems and systems used for image processing/analysis.
FIG. 1 provides an example of two images of the same subject matter, e.g., a group of objects, a triangle 11, a circle 12, a rectangle 13, and a square 14, that may be the subject of image registration. That is, FIG. 1 includes a first image 10 and a second image 20. Further, although the two images 10, 20 do not present the same alignment of the image relative to the objects there is a considerable amount of overlap between the images. For example, the circle 12 appears in its entirety in each of the first and second images 10, 20, while at least a portion of each of the triangle 11, the rectangle 13 and the square 14 appear in each image 10, 20.
FIG. 2 illustrates an example in which the first image 10 is geometrically transformed to map the first image 10 relative to the second image 20. That is, positions in the first image are transformed into positions in the second image 20 or vice versa. Such a transformation is often referred to as a warp operation and generally results in the coordinates of each position in the first image 10 being transformed by some amount to convert them to coordinates in the second image 20. Of course, the transformation may instead operate to transform the coordinates of each position in the second image to convert them to coordinates in the first image 10.
As illustrated in FIG. 2, there may be regions of the first image 15, 16, 17 and regions of the second image 21, 22, 23 that do not correspond to any region of the other image. Generally, positions in these “non-overlapping” regions are not mapped because of the lack of correspondence. That is, these regions generally do not provide information that is useful in transforming the positions in the first image 10 to corresponding positions in the second image because no such correspondence exists.
Image alignment can be performed on a first and a second image using a transformation process whereby a first image is “moved” through a variety of positions/changes in orientation relative to a second image. That is, at least one of the images undergoes a geometrical transformation, e.g., warping. The transformation process may vary the parameters (“transformation parameters”) employed to move the first image through a variety of positions/orientations until a close (e.g., an identical match) or otherwise optimal alignment is achieved between the first image and the second image. A transformation can be represented using various parameters. For example, a transformation can be represented using parameters for each of a: translation in the x direction; translation in the y direction; rotation; scale change in the x direction; scale change in the y direction; perspective change in the x direction; perspective change in the y direction; and shearing.
Generally, a transformation is performed as a mathematical operation in which the coordinates in the first image are transformed into corresponding coordinates in the second image or vice versa. As explained below, transformation processes may operate on image coordinates represented in a vector format. FIG. 3 illustrates an approach in which coordinates in two images, image A and image B may be represented mathematically and associated with one another in a common coordinate system to facilitate a transformation of an image. Some images can be represented mathematically as a 2 dimensional function I(x, y) or, in vector form, I(x) defined over a domain D. The vector x=(x y)T represents a position in the image expressed relative to a coordinate system of the image. The coordinate system is sometimes referred to as the basis of the image. For a grayscale image, I(x) represents the grayscale intensity at position x of the image. For a digital image, I(x) is a discrete function defined for integer values of x and y. However, I(x) can be extended to a continuous function over the domain D by interpolation, e.g. bilinear interpolation.
In the case of two or more images that are not aligned, the images will have different domains and consequently a different set of coordinates. In FIG. 3, the first image A is defined over a first domain DA and a second image B is defined over a second domain DB. (The domains DA and DB are represented by the shaded areas that appear in FIG. 4.) As illustrated in FIG. 3, the first image A is offset both horizontally and vertically relative to the second image B. Accordingly, a translation in both the x direction and the y direction is required to locate in the second image B the position corresponding to the position x1, y1 of the first image A. That is, the position x1, y1 may be expressed in a first coordinate system BA or a second coordinate system BB. As illustrated here, the transformation may involve a shift of various of the translation parameters identified above (i.e., an x translation and a y translation in the example illustrated in FIG. 3).
Various prior art approaches have been proposed to find a transformation that aligns two images. Some of these approaches employ a process that includes a minimization algorithm to minimize the difference between the images to find the best alignment, that is, to determine the set of transformation parameters that most closely align the images. However, these prior art approaches employ the intensity level difference on a pixel by pixel basis across the entire image to determine how well the first and second image are aligned, that is, how closely the intensity levels of the images are matched. Because these approaches are not effective unless the user has a very good initial estimate of the transformation parameters, these approaches generally reduce the level of detail in the images (i.e., smooth the images) before being processed by the algorithm to allow the algorithm to converge to the correct solution. As a result, these approaches may eliminate details that would have been useful in properly aligning the images.
Other approaches evaluate the registration of images by evaluating regions within the images. These approaches attempt to minimize a distance between matched regions. As a result, proper alignment is determined based on the separation distance. However, these approaches fail to take into account characteristics of a match between regions. For example, these approaches do not address the quality of a region-match nor its strength as a first region is shifted in any one of a plurality of directions relative to a second region with which it is being matched.
Current approaches also fail to provide a method to reduce or minimize the quantity of regions that should be matched to provide an optimal alignment between images.